package Bi_Tree;

import java.util.*;

public class lc222 {
    public int countNodes(TreeNode root) {
        //输入输出  根节点；节点个数
        //终止条件：root==null
        if(root==null){
            return 0;
        }
        //单层逻辑
        int left=countNodes(root.left);
        int right=countNodes(root.right);
        return left+right+1;

    }
    public int countNodes1(TreeNode root) {  //前序遍历
        if(root==null) return 0;
       Stack<TreeNode> stack=new Stack<>();
        TreeNode node=root;
        stack.push(node);
        int count=0;
        while (!stack.isEmpty()){
            node=stack.pop();
            count++;
            if(node.right!=null) stack.push(node.right);
            if(node.left!=null) stack.push(node.left);
        }
        return count;
    }

    public int countNodes_level(TreeNode root) {  //层次遍历
        if(root==null) return 0;
        Queue<TreeNode> queue=new LinkedList<>();
        List<List<Integer>> list=new ArrayList<>();
        TreeNode node=root;
        queue.offer(node);
       // int count=0;
        while (!queue.isEmpty()){
            List<Integer> smalllist=new ArrayList<>();
            int len= queue.size();
            while (len>0){
                node=queue.poll();
            //    count++;
                smalllist.add(node.val);
                if(node.left!=null) queue.offer(node.left);
                if(node.right!=null) queue.offer(node.right);
                len--;
            }
            list.add(smalllist);
        }
        int le= list.size();
        double count=Math.pow(2,le-1)-1;
        count+=list.get(le-1).size();
        return (int) count;

    }

}
